package org.chnxi.study.datastructrues.search;

import java.util.Arrays;

/**
 * 插值查找
 */
public class InsertValSearching {

    public static void main(String[] args) {
        int size = 100;
        int[] arr = new int[size];
        for (int i = 1 ; i <= size; i++){
            arr[i-1] = i;
        }


        System.out.println("数组中数据："+ Arrays.toString(arr));

        int idx = insertValSearch(arr , 0 , arr.length -1 , 47);

        System.out.println("查找结果，index="+idx);
    }

    /**
     *
     * @param arr 数组
     * @param left 左边索引
     * @param right 右边索引
     * @param findVal 查找值
     * @return 未找到返回 -1，找到返回索引
     */
    public static int insertValSearch(int[] arr , int left , int right , int findVal){
        System.out.println("执行查找...");
        if(left > right || findVal < arr[0] || findVal >arr[arr.length-1]){
            return -1;
        }

        //与二分查找区别主要在这里
        int mid = left = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);
        int midVal = arr[mid];

        if(findVal > midVal){ //向右找
            return insertValSearch(arr , mid+1 , right , findVal);
        }else if(findVal < midVal){ //向左找
            return insertValSearch(arr , left , mid-1, findVal);
        }else{
            return mid;
        }
    }

}
